

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//ctl alt t包裹
public class Test{
    //字符串转数组,数组转字符串
    //字符串内容比较
    public static void main1(String[] args) {
        Stack<Character> stack=new Stack<>();
        Scanner scanner=new Scanner(System.in);
        String str=scanner.next();
        for (int i = 0; i <str.length() ; i++) {
            stack.push(str.charAt(i));
        }
        char[] array=new char[str.length()];
        for (int i = 0; i <str.length() ; i++) {
            array[i]=stack.pop();
        }

        String str2=new String(array);

//        StringBuffer sb=new StringBuffer();
//        for (int i = 0; i <array.length ; i++) {
//            sb.append(array[i]);
//        }
//        boolean b= str.equals(sb);
        System.out.println(str.equals(str2));

    }
//删除两个字符串中的公共字符
    public static void main2(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String str1=scanner.nextLine();
        String str2=scanner.nextLine();

        char[] arr1=new char[str1.length()];
        for (int i = 0; i <str1.length() ; i++) {
            arr1[i]=str1.charAt(i);
        }
        int size=arr1.length;
        for (int i = 0; i <arr1.length ; i++) {
            for (int j = 0; j <str2.length() ; j++) {
                if(arr1[i]==str2.charAt(j)){
                    for (int k = i; k <arr1.length-1 ; k++) {
                        arr1[k]=arr1[k+1];
                    }
                    size--;
                }
            }
        }
        char[] arr2=new char[size];
        for (int i = 0; i <size ; i++) {
            arr2[i]=arr1[i];
        }
        String str3=new String(arr2);
        System.out.println(str3);
    }

    public static void main3(String[] args) {
        Scanner scanner=new Scanner(System.in);

        while (scanner.hasNext()){
            String str=scanner.nextLine();
            int max=0,count=0,end=0;
            for (int i = 0; i <str.length() ; i++) {
                if(str.charAt(i)>='0'&&str.charAt(i)<='9'){
                    count++;
                    if(max<count){
                        max=count;
                        end=i;
                    }
                }else {
                    count=0;
                }
            }
            System.out.println(str.substring(end-max+1,end+1));
        }
    }

    public static void main4(String[] args) {
        int[]arr={3,3,3,3,2,2,2};
        int ret=MoreThanHalfNum_Solution(arr);
        System.out.println(ret);
    }
    //数组中次数超过一半的数字
    public static int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);//sort的用法
        int count=0;
        int max=0;int maxnum=0;
        if(array.length==1){
            maxnum=array[0];
        }
        for (int i = 0; i+1 <array.length ; i++) {
            if(array[i]==array[i+1]){
                count++;
                if(max<count){
                    max=count;
                    maxnum=array[i];
                }
            }else {
                count=0;
            }
        }
        return maxnum;
    }
    //组队竞赛
    /*
    先排序,第一个和倒数一二个为一组,第二个和倒数三四个为一组,以此类推分组
     */
    public static void main5(String[] args) {
        Scanner scan=new Scanner(System.in);
        while (scan.hasNextInt()){
            int n=scan.nextInt();
            int[]arr=new int[3*n];
            for (int i = 0; i <3*n ; i++) {
                arr[i]=scan.nextInt();
            }
            Arrays.sort(arr);
            long sum=0;
            for (int i = 0; i <n ; i++) {
                sum+=arr[arr.length-2*(i+1)];//取的是每组的平均战力(先排序后从到数第二个开始取,取一个减2)
            }
            System.out.println(sum);
        }
    }
    //统计回文
    public static boolean isHuiwen(String str){
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i <str.length() ; i++) {
            stack.push(str.charAt(i));
        }
        char[]array=new char[str.length()];
        for (int i = 0; i <str.length() ; i++) {
            array[i]=stack.pop();
        }
        String str2=new String(array);
        if (str.equals(str2)) {
            return true;
        }else {
            return false;
        }

    }
    public static void main6(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String str1=scanner.nextLine();
        String str2=scanner.nextLine();
        int count=0;
        for (int i = 0; i <=str1.length() ; i++) {
            if(i==0){
                String str3=str2+str1;
                if(isHuiwen(str3)) count++;
            }else if(i==str1.length()){
                String str3=str1+str2;
                if(isHuiwen(str3)) count++;
            }else{
                String str3=str1.substring(0,i)+str2+str1.substring(i,str1.length());
                if(isHuiwen(str3)) count++;
            }
        }
        System.out.println(count);
    }
    //
    public static int sum(int[]array,int start,int end){
        int sum=0;
        for (int i = start; i <=end ; i++) {
            sum+=array[i];
        }
        return sum;
    }
    public static void main7(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int[] array=new int[n];
        for(int i=0;i<array.length;i++){
            array[i]=scan.nextInt();
        }
        int max=array[0];
        for (int i = 0; i <array.length ; i++) {
            for (int j = i; j <array.length ; j++) {
                int sum= sum(array,i,j);
                if(max<sum){
                    max=sum;
                }
            }
        }

        System.out.println(max);
        //System.out.println(Arrays.toString(array2));
        
    }
    //计算糖果
    private static boolean isSingular(int a){
        if(a%2==0) return false;
        return true;
    }
    public static void main8(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int[] array=new int[4];
        for (int i = 0; i <array.length ; i++) {
            array[i]=scanner.nextInt();
        }

        int A=(array[0]+array[2])/2;
        int B=(array[1]+array[3])/2;
        int C=array[3]-B;
        if(isSingular(array[0]+array[2])){
            System.out.println("No");
        }else if(isSingular(array[1]+array[3])){
            System.out.println("No");
        }else if(A<0||B<0||C<0){
            System.out.println("No");
        }else {
            System.out.println((int)A+" "+(int)B+" "+(int)C);
        }
    }
    //删除公共字符hashmap
    //用hash映射的思想
    public static void main9(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String str1=scanner.nextLine();
        String str2=scanner.nextLine();
        HashMap<Character,Integer> hashMap=new HashMap<>();
        //遍历str2
        for (int i = 0; i <str2.length() ; i++) {
            //拿到当前字符判断是否已存在在当前map中
            if(hashMap.get(str2.charAt(i))==null){
                //不存在在该位置上设为1
                hashMap.put(str2.charAt(i),1);
            }else {
                //存在在该位置上++
                hashMap.put(str2.charAt(i),hashMap.get(str2.charAt(i))+1);
            }
        }
        String str="";
        //遍历str1,如果字母没出现在map中就取出
        for (int i = 0; i <str1.length() ; i++) {
            if(hashMap.get(str1.charAt(i))==null){
                str+=str1.charAt(i);
            }
        }
        System.out.println(str);
    }
    //删除公共字符
    public static void main10(String[] args) {
        int[] hash=new int[256];
        Scanner scanner=new Scanner(System.in);
        String str1=scanner.nextLine();
        String str2=scanner.nextLine();
        for (int i = 0; i <str2.length() ; i++) {
            hash[str2.charAt(i)]++;
        }
        String str="";
        for (int i = 0; i <str1.length() ; i++) {
            if(hash[str1.charAt(i)]==0){
                str+=str1.charAt(i);
            }
        }
        System.out.println(str);
    }
    //计算糖果
    public static void main11(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int a=scanner.nextInt();
        int b=scanner.nextInt();
        int c=scanner.nextInt();
        int d=scanner.nextInt();
        int A=(a+c)/2;
        int B1=(b+d)/2;
        int B2=(c-a)/2;
        int C=(d-b)/2;
        if(B1!=B2){
            System.out.println("No");
        }else{
            System.out.println(A+" "+B1+" "+C);
        }
    }
    //进制转换
    //辗转相除法
    public String solve (int M, int N) {
        // write code here
        String table="0123456789ABCDEF";
        StringBuilder str=new StringBuilder();//更高效
        boolean flag=false;
        if(M<0){
            M=-M;//如果是负数先置为正值
            flag=true;
        }
        while (M!=0){
            str.append(table.charAt(M%N));//此处取余
            M/=N;
        }
        if(flag){
            str.append("-");//将负号放到字符串末尾
        }
        str.reverse();//逆置(倒取)
        String ret=new String(str);
        return ret;
    }
    //把字符串转为整数
    private static int StrToInt(String str) {
        if(str.length()==0) return 0;
        if (str==null) return 0;
        if (str=="0") return 0;
        int num=0;
        if(str.charAt(0)!=43&&str.charAt(0)!=45){
            str="+"+str;
        }
        int[] arr=new int[str.length()-1];
        for (int i=1;i<str.length();i++){
            if(str.charAt(i)<48||str.charAt(i)>57){
                return 0;
            }
            int a=(str.charAt(i)-48);
            arr[i-1]=a;
        }
        for (int i = 0; i <arr.length ; i++) {
            num+=arr[i];
            if(i!=arr.length-1){
                num*=10;
            }
        }
        if (str.charAt(0) == 45) {
            num=-num;
        }
        return num;
    }

    public static void main12(String[] args) {
        String str="+2147483647";
        int ret=StrToInt(str);
    }
    //动态规划 求连续子数组最大和
    public static int getMax(int a, int b){
        return a>b?a:b;
    }
    public static void main13(String[] args){
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int[] array=new int[n];
        for(int i=0;i<n;i++){
            array[i]=scan.nextInt();
        }
        int sum=array[0];
        int max=array[0];
        for(int i=1;i<n;i++){//从下标为1开始算
            sum=getMax(sum+array[i],array[i]);//前i-1个最大子数组的和,与第i个元素相比谁大=前i个最大子数组的和
            if(sum>max){
                max=sum;//找出最大连续子数组的和
            }
        }
        System.out.print(max);
    }
    //统计回文
    public static void main14(String[] args) {
        Scanner scan=new Scanner(System.in);
        String str1=scan.nextLine();
        String str2=scan.nextLine();
        int count=0;
        for(int i=0;i<=str1.length();i++){
            StringBuffer str3=new StringBuffer(str1);
            str3.insert(i,str2);
            StringBuffer tmp=new StringBuffer(str3);
            StringBuffer str4=tmp.reverse();//str3也被逆置了
            if(str4.toString().equals(str3.toString())){//StringBuffer没有equals方法
                count++;
            }
        }
        System.out.println(count);
    }
    //字符串中找出连续最长的数字串
    public static void main15(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String str=scanner.nextLine();
        String cur="";
        String ret="";
        int i = 0;
        for (; i <str.length() ; i++) {
            char ch=str.charAt(i);
            if(ch>='0'&&ch<='9'){
                cur=cur+ch+"";
            }else {
                if(cur.length()>ret.length()){
                    ret=cur;
                }else {
                    cur="";
                }
            }
        }
        if(cur.length()>ret.length()){
            ret=cur;
        }
        System.out.println(ret);
    }
    //数组中出现次数超过一半的数
    //众数抵消发
    private int MoreThanHalfNum_Solution2(int [] array) {
        if(array==null||array.length==0) return 0;
        int times=1;
        int result=array[0];
        //如果有众数最后的result一定是超过一半的数
        for (int i = 1; i <array.length ; i++) {
            if(times!=0){
                if(result==array[i]){
                    ++times;
                }else {
                    --times;
                }
            }else {
                result=array[i];
                times=1;
            }
        }
        int count=0;
        for (int i = 0; i < array.length; i++) {//判断result出现次数是否超过数组一半
            if(array[i]==result) count++;
        }
        if(count>(array.length/2)) return result;
        return 0;
    }
    //合法括号序列判断
    private static boolean chkParenthesis(String A, int n) {
        // write code here
        Stack<Character> stack=new Stack<>();
        char tmp='0';
        for (int i = 0; i <A.length() ; i++) {
            if(A.charAt(i)=='('||A.charAt(i)=='['||A.charAt(i)=='{'){
                stack.push(A.charAt(i));
            }else {
                if(stack.empty()) return false;//右括号多于左括号
                 tmp=stack.peek();
                if((tmp=='('&&A.charAt(i)==')')||(tmp=='['&&A.charAt(i)==']')||(tmp=='{'&&A.charAt(i)=='}')){//括号不匹配
                    stack.pop();
                }else {
                    return false;
                }
            }

        }
        if(!stack.empty()) return false;//左括号多于右括号
        return true;
    }
    //不要二
    public static void main16(String[] args) {
        Scanner scan=new Scanner(System.in);
        int w=scan.nextInt();
        int h=scan.nextInt();
        int[][] array=new int[w][h];
        int count=0;
        for(int i=0;i<w;i++){
            for(int j=0;j<h;j++){
                if(array[i][j]==0){//可以放蛋糕
                    count++;
                    if(i+2<w){
                        array[i+2][j]=1;//距离为2的位置置为1,注意越界问题(表示不能放蛋糕)
                    }
                    if(j+2<h){
                        array[i][j+2]=1;
                    }
                }
            }
        }
        System.out.print(count);
    }
    //把字符串转为数字
    public int StrToInt2(String str) {
        if(str.isEmpty()){
            return 0;
        }
        int flag=0;
        if(str.charAt(0)=='-'){
            flag=-1;
        }else if(str.charAt(0)=='+'){
            flag=1;
        }else{
            str='+'+str;
            flag=1;
        }
        int num =0;
        for(int i=1;i<str.length();i++){
            if(str.charAt(i)<'0'||str.charAt(i)>'9'){
                num=0;
                break;
            }
            num=num*10+str.charAt(i)-'0';
        }
        return num*flag;
    }
    //求最小公倍数
    public static void main17(String[] args){
        Scanner scan=new Scanner(System.in);
        int A=scan.nextInt();
        int B=scan.nextInt();
        int max=A>B?A:B;
        int min=A<B?A:B;
        int num=0;
        for(int i=1;i<=min;i++){
            if((max*i)%min==0){
                num=max*i;
                break;
            }
        }
        System.out.print(num);
    }
    //变为斐波那契额数的最小步数
    /*
    斐波那契额数要不比n小要不大于等n
    只要找出大于等于n的斐波那契数就可以找到n两边的斐波那契数
    找出与n最近的斐波那契数与n做差即可算出最小步数
     */
    public static void main18(String[] args){
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int f1=0,f2=1;
        int fibo=0;
        while(fibo<=n){
            fibo=f1+f2;
            f1=f2;
            f2=fibo;
        }
        int count=Math.min(fibo-n,n-f1);
        //int count=(fibo-n)>(n-f1)?(n-f1):(fibo-n);
        System.out.print(count);
    }
    //另类加法
    static int addAB(int A, int B) {
        // write code here
        while (B!=0){//直至不需要进位
            int sum=A^B;//不需要进位加之后的结果
            int and=(A&B)<<1;//按位与之后得进位
            A=sum;//之后进位和不进位加的结果继续加
            B=and;//(进位
        }
        return A;
    }

    public static void main24(String[] args) {
        System.out.println(addAB(2,3));
    }
    //密码强度等级
    public static void main19(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNextLine()){
            String password=scan.nextLine();
            int ret=level(password);
            if(ret>=0&&ret<25) System.out.println("VERY_WEAK");
            if(ret>=25&&ret<50) System.out.println("WEAK");
            if(ret>=50&&ret<60) System.out.println("AVERAGE");
            if(ret>=60&&ret<70) System.out.println("STRONG");
            if(ret>=70&&ret<80) System.out.println("VERY_STRONG");
            if(ret>=80&&ret<90) System.out.println("SECURE");
            if(ret>=90) System.out.println("VERY_SECURE");

        }
    }
    private static int level(String password){
        int num=0;
        if(password.length()<=4)  num+=5;
        if(password.length()<=7&&password.length()>=5)  num+=10;
        if(password.length()>=8) num+=25;

        int flg=0;
        int A=0;
        int a=0;
        int count=0;
        int sym=0;
        for(int i=0;i<password.length();i++){
            if(password.charAt(i)>='A'&&password.charAt(i)<='Z'){
                flg++;
                A=1;
            }
            if(password.charAt(i)>='a'&&password.charAt(i)<='z'){
                flg++;
                a=1;
            }
            if(password.charAt(i)>='0'&&password.charAt(i)<='9'){
                count++;
            }
            if(password.charAt(i)>=0x21&&password.charAt(i)<=0x2f){
                sym++;
            }
            if(password.charAt(i)>=0x3a&&password.charAt(i)<=0x40){
                sym++;
            }
            if(password.charAt(i)>=0x5b&&password.charAt(i)<=0x60){
                sym++;
            }
            if(password.charAt(i)>=0x7b&&password.charAt(i)<=0x7e){
                sym++;
            }
        }
        if(flg==0) num+= 0;
        if((a==0&&A!=0)||(a!=0&&A==0)) num+=10;
        if(a==1&&A==1) num+=20;
        if(count==0) num+=0;
        if(count==1) num+=10;
        if(count>1) num+=20;
        if(sym==0) num+=0;
        if(sym==1) num+=10;
        if(sym>1) num+=25;
        if(flg>=1&&count>=1&&sym>=1&&a==1&&A==1) {
            num+=5;
        }else if(flg>=1&&count>=1&&sym>=1){
            num+=3;
        }else if(flg>=1&&count>=1){
            num+=2;
        }
        return num;
    }


    public static void main20(String[] args) {
        System.out.println(new B().getValue());
        //new B().getValue()最终的返回值是17.
    }
    static class A {
        protected int value;
        public A (int v) {
            setValue(v);
        }
        public void setValue(int value) {//一开始没调用这个
            this.value= value;//得到22后调用这个
        }
        public int getValue() {//value=10
            try {
                value ++;
                return value;//value=11(被缓存),return
            } finally {//无论如何都会执行
                this.setValue(value);//调用的是类的setValue方法
                                     //因为此刻正在初始化的是B类的一个对象
                                     //this关键词显式指明了调用当前对象的方法,当前对象是B
                System.out.println(value);//打印22(new B()构造一个B类的实例) 34
            }
        }
    }
    static class B extends A {
        /*
此时super(5)语句调用显示调用父类A带参的构造函数，该构造函数调用setValue(v)，
这里有两个注意点一是虽然构造函数是A类的构造函数，但此刻正在初始化的对象是B的一个实例，
因此这里调用的实际是B类的setValue方法
         */
        public B () {//Step 1:  new B()构造一个B类的实例
            super(5);
            setValue(getValue()- 3);//继续执行setValue(getValue()- 3)
            //先执行getValue方法，B类中没有重写getValue方法，因此调用父类A的getValue方法。
        }
        public void setValue(int value) {
            super.setValue(2 * value);//而B类中setValue方法显示调用父类的setValue方法
                                      //将B实例的value值设置为2 x 5 = 10。
                                      //value变为22
        }
    }
//求二进制中连续1的个数 int表示32位bit位
    public static void main21(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNextInt()){
            int n=scan.nextInt();
            System.out.println(count(n));
        }
    }
    private static int count(int n){
        int count=0;
        int max=0;
        for(int i=0;i<32;i++){//32不是8
            if((n&1)==1){
                count++;
            }
            if((n&1)==0){
                count=0;
            }
            if(count>max){
                max=count;
            }
            n= n>>1;
        }
        return max;
    }
    //按照长度排序和按照字母排序
    public static void mai21(String[] args) throws IOException, IOException {
        //BufferedReader从字符流中读取文本并缓存
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(reader.readLine());
        String[] str=new String[n];
        for(int i=0;i<n;i++){
            str[i]=reader.readLine();
        }
        boolean ret1=isSortZidian(str);
        boolean ret2=isSortLength(str);
        if(ret1&&!ret2){
            System.out.println("lexicographically");
        }
        if(!ret1&&ret2){
            System.out.println("lengths");
        }
        if(ret1&&ret2){
            System.out.println("both");
        }
        if(!ret1&&!ret2){
            System.out.println("none");
        }
    }
    private static boolean isSortLength(String[] str){
        for(int i=0;i<str.length-1;i++){
            if(str[i].length()>str[i+1].length()){
                return false;
            }
        }
        return true;
    }
    private static boolean isSortZidian(String[] str){
        for(int i=0;i<str.length-1;i++){
            if(str[i].compareTo(str[i+1])>0){//直接调用String.compareTo,按照字母顺序排序
                return false;
            }
        }
        return true;
    }
    //求最小公倍数
    /*
    最小公倍数=m*n/(m和n的最大公约数)
     */
    public static void main22(String[] args){
        Scanner scan=new Scanner(System.in);
        int m=scan.nextInt();
        int n=scan.nextInt();
        int mn=gbc(m,n);
        System.out.println(m*n/mn);
    }
    private static int gbc(int m,int n){//求最大公约数,辗转相除法
        if(m==n) return m;
        if(m<n){
            int tmp=m;
            m=n;
            n=tmp;
        }
        int r=0;
        while((r=m%n)>0){
            m=n;
            n=r;
        }//余数为零后取除数
        return n;
    }
    //走方格的方案数
    /*
    m行,n列
    总方案数=(m-1)行n列方案数+m行(n-1)列方案数
    当m==1||n==1时方案数=m+n
     */
    public static void main23(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNextInt()){
            int m=scan.nextInt();
            int n=scan.nextInt();
            System.out.println(count(m,n));
        }
    }
    private static int count(int m,int n){
        if(m==1||n==1) return m+n;
        return count(m-1,n) +count(m,n-1);
    }
    //判断井字棋是否赢
    public boolean checkWon(int[][] board) {
        // write code here
        if(board[0][0]+board[1][1]+board[2][2]==3) return true;
        if(board[0][2]+board[1][1]+board[2][0]==3) return true;
        for(int i=0;i<3;i++){
            if(board[i][0]+board[i][1]+board[i][2]==3) return true;
            if(board[0][i]+board[1][i]+board[2][i]==3) return true;
        }
        return false;
    }
    //查找组成一个偶数最接近的两个素数
    //这两个素数之和为这个偶数
    public static void main26(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNextInt()){
            int n=scan.nextInt();
            int[] ret=new int[2];
            for(int i=2;i<=n/2;i++){
                if(isPrime(i)&&isPrime(n-i)){//两个素数不断接近
                    ret[0]=i;
                    ret[1]=n-i;
                }
            }
            System.out.println(ret[0]);
            System.out.println(ret[1]);
        }
    }
    private static boolean isPrime(int n){
        for(int i=2;i<n/2;i++){
            if(n%i==0) return false;
        }
        return true;
    }

    //二进制插入
    /*
    保证n的第j到第i位均为零
              i   j
    1024：100000000 00
    19 ：     10011
    可以看到上面得出，只要我们用1011与1024的第j位到第i位做或运算（|）即可。
    我们想到可以让10011左移j位就可以正常做运算了。
    10000000000
    00001001100
     */
    public class BinInsert {
        public int binInsert(int n, int m, int j, int i) {
            // write code here
            for(int x=0;x<j;x++){
                m=m<<1;
            }
            return n|m;
        }
    }
    //判断井字棋是否胜利
    public boolean checkWon2(int[][] board) {
        // write code here
        //斜向是否连成线
        if(board[0][0]+board[1][1]+board[2][2]==3) return true;
        if(board[0][2]+board[1][1]+board[2][0]==3) return true;
        for(int i=0;i<3;i++){
            if(board[i][0]+board[i][1]+board[i][2]==3) return true;//横向是否连成线
        }
        for(int j=0;j<3;j++){
            if(board[0][j]+board[1][j]+board[2][j]==3) return true;//纵向是否连成线
        }
        return false;
    }
    //求最近公共祖先
    /*
    完全二叉树:parent=child/2
    如果两个数相等祖先为其中一个
    如果两个数不相等从较大的那个孩子开始找祖先,看祖先是否和另一个孩子相同,如果不是再从新的祖先和另一个孩子中较大的那个数开始找祖先
    依次向上找直至两数相等即为最近公共祖先
     */
    private static int getLCA(int a, int b) {
            // write code here
            if(a==b) return a;
            while(true){
                if(a>b){
                    a/=2;
                    if(a==b){
                        return a;
                    }
                }
                if(b>a){
                    b/=2;
                    if(a==b){
                        return a;
                    }
                }
            }
        }
        //更简洁的写法
    private static int getLCA2(int a, int b) {
        // write code here
        while(a!=b){
            if(a>b){
                a=a/2;
            }else{
                b=b/2;
            }
        }
        return a;
    }
    //输入日期计算是这一年的第几天
    public static void main25(String[] args){
        Scanner scan = new Scanner(System.in);
        int year=0;
        int month=0;
        int day=0;
        while(scan.hasNextInt()){
            year = scan.nextInt();
            month = scan.nextInt();
            day = scan.nextInt();
        }
        int num=0;
        int flg=0;
        int count=0;
        if((year%4==0&&year%100!=0)||year%400==0){
            flg=1;
        }
        if(flg==1){
            count=29;
        }else{
            count=28;
        }
        if(month==1){
            System.out.println(day);
        }else if(month==2){
            System.out.println(31+day);
        }else if(month==3&&flg==0){
            System.out.println(count+31+day);
        }else if(month==4){
            System.out.println(count+62+day);
        }else if(month==5){
            System.out.println(count+92+day);
        }else if(month==6){
            System.out.println(count+123+day);
        }else if(month==7){
            System.out.println(count+153+day);
        }else if(month==8){
            System.out.println(count+184+day);
        }else if(month==9){
            System.out.println(count+215+day);
        }else if(month==10){
            System.out.println(count+245+day);
        }else if(month==11){
            System.out.println(count+276+day);
        }else if(month==12){
            System.out.println(count+306+day);

        }
    }
    //跳石板
    public static void main27(String[] args){
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int m=scan.nextInt();
        int[] step=new int[m+1];
        //初始化石板
        for(int i=0;i<step.length;i++){
            step[i]=Integer.MAX_VALUE;
        }
        step[n]=0;//里面放的是跳了几步
        for(int i=n;i<m;i++){
            if(step[i]==Integer.MAX_VALUE){//没有跳到的石板不管它
                continue;
            }
            List<Integer> list=divisor(i);
            for (int j: list) {
                if(i+j<=m&&step[i+j]!=Integer.MAX_VALUE){//已经跳到不止一次了
                    step[i+j]=Math.min(step[i+j],step[i]+1);//对比原来的值和再走一步的指哪个更大
                }else if(i+j<=m){
                    step[i+j]=step[i]+1;//第一次跳到这
                }
            }
        }
        if(step[m]!=Integer.MAX_VALUE){
            System.out.println(step[m]);
        }else {
            System.out.println(-1);
        }
    }
    private static List<Integer> divisor(int n){
        List<Integer> list=new ArrayList<Integer>();
        for (int i = 2; i*i <=n ; i++) {
            if(n%i==0){
                list.add(i);
                if(i!=n/i){
                    list.add(n/i);
                }
            }

        }
        return list;
    }
    //参数解析
    public static void main28(String[] args){
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        int count = 0;//空格数+1等于命令数
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)=='"'){//遍历引号内的内容(包含空格的命令)
                do{
                    i++;
                }while(str.charAt(i)!='"');
            }
            if(str.charAt(i)==' '){
                count++;
            }
        }
        System.out.println(count+1);
        int flg=0;
        for(int i=0;i<str.length();i++){
            //flg=0是引号外的内容
            //flg=1是引号内的内容
            if(str.charAt(i)=='"'){
                flg=flg^1;
            }
            if(str.charAt(i)!='"'&&str.charAt(i)!=' '){
                System.out.print(str.charAt(i));//打印字符
            }
            if(flg==1&&str.charAt(i)==' '){
                System.out.print(str.charAt(i));//打印引号内的空格
            }
            if(flg==0&&str.charAt(i)==' '){//引号外用于区分命令的空格
                System.out.println();//需换行
            }
        }
    }
    //查找输入整数二进制中1的个数
    public static void main29(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNextInt()){
            int n=scan.nextInt();
            System.out.println(count_1(n));
        }
    }
    private static int count_1(int n){
        int count=0;
        while(n!=0){
            if((n&1)==1){
                count++;
            }
            n=n>>1;
        }
        return count;
    }
    public static void  main30(String[] args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextInt()){
            System.out.println(wanshu(scan.nextInt()));
        }
    }
    private static int wanshu(int n){
        int count=0;
        for(int i=n-1;i>0;i--){
            int sum=0;
            for(int j=i-1;j>0;j--){
                if(i%j==0){
                    sum+=j;
                }
            }
            if(sum==i){
                count++;
            }
        }
        return count;
    }

//幸运袋子
    public static void main31(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] array=new int[n];
        for(int i=0;i<array.length;i++){
            array[i]=scanner.nextInt();
        }
        Arrays.sort(array);//要记得排序
        System.out.println(count(array,0,0,1));
    }
    private static int count(int[] array,int port,int sum,int mul){
        int count=0;
        for (int i = port; i < array.length; i++) {//注意i=port
            sum+=array[i];
            mul*=array[i];
            if(sum>mul){
                count=count+1+count(array,i+1,sum,mul);
            } else if(array[i]==1){//比如1 1 2 3
                                  //array[0]=1,sum=1,mul=1,就得继续加(1与任何数的和都大于1与任何数的积)
                count+=count(array,i+1,sum,mul);
            }else {
                break;//找到不能组成幸运袋子的球了,直接break
            }
            //进行回溯
            sum-=array[i];
            mul/=array[i];
            while (i+1<array.length&&array[i]==array[i+1]){
                i++;//有相同(不能组成幸运袋子)的球,要跳过不然就卡住了
            }
        }
        return count;
    }
    //变相杨辉三角
    /*
    找规律,行数为1,2没有偶数
    行数为4的倍数的偶数行第一个偶数在3位置
    行数不为4的倍数的偶数行第一个偶数在4位置
    奇数行第一个偶数在2位置
     */
        public static void main32(String[] args){
            Scanner scan=new Scanner(System.in);
            while(scan.hasNextInt()){
                int n=scan.nextInt();
                if(n<=2){
                    System.out.println(-1);
                }else if(n%2!=0){
                    System.out.println(2);

                }else if(n%4==0){
                    System.out.println(3);
                }else if(n%4!=0){
                    System.out.println(4);
                }
            }
        }


    //手套
    public static void main33(String[] args) {
            int[] a={0,7,1,6};
            int[] b={1,5,0,6};
            System.out.println(findMinimum(4,a,b));
    }
    private static int findMinimum(int n, int[] left, int[] right) {
        // write code here
        int sum=0;//同种颜色只有一只的手套数
        int leftSum=0;
        int rightSum=0;
        int leftMin=Integer.MAX_VALUE;
        int rightMin=Integer.MAX_VALUE;
        for (int i = 0; i <n ; i++) {
            if(left[i]==0||right[i]==0){
                sum+=left[i]+right[i];
            }else {
                rightSum += right[i];
                leftSum += left[i];
                if (left[i] < leftMin) {
                    leftMin = left[i];
                }
                if (right[i] < rightMin) {
                    rightMin = right[i];
                }
            }
        }
        return Math.min(leftSum-leftMin+1,rightSum-rightMin+1)+1+sum;//leftSum-leftMin+1除单只手套外左边拿满所有颜色手套的最少手套数
                                                                     //rightSum-rightMin+1除单只手套外有边拿满所有颜色手套的最少手套数
                                                                     //+1:找出以上两个哪个最小后拿另一只手的一只手套
                                                                     //+sum把单只的手套都拿上确保拿到的手套一定有成双的
    }
    //扑克牌大小
    public static void main34(String[] args){
        Scanner scan=new Scanner(System.in);
        String str=scan.nextLine();
        String[] pp=str.split("-");
        String[] p1=pp[0].split(" ");//pp[0]是第一手牌,pp[1]是第二手牌
        String[] p2=pp[1].split(" ");
        String p="34567891JQA2";
        if(pp[0].equals("joker JOKER")||pp[1].equals("joker JOKER")){//注意细节
            System.out.println("joker JOKER");
        }else if(p1.length==p2.length){
            if(p.indexOf(p1[0].substring(0,1))>p.indexOf(p2[0].substring(0,1))){
                System.out.println(pp[0]);
            }else{
                System.out.println(pp[1]);
            }
        }else if(p1.length==4){
            System.out.println(pp[0]);
        }else if(p2.length==4){
            System.out.println(pp[1]);
        }else{
            System.out.println("ERROR");
        }
    }
    //统计每个月兔子总数
    public static void main35(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNextInt()){
            int n=scan.nextInt();
            System.out.println(number(n));
        }
    }
    private static int number(int n){
        if(n==1||n==2){
            return 1;
        }
        return number(n-1)+number(n-2);
    }

    //汽水凭
    public static void main36(String[] args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextInt()){
            int n=scan.nextInt();
            if(n==0){
                break;
            }
            System.out.println(count2(n));
        }
    }
    private static int count2(int n){
        if(n/3==0) return 0;
        int water=n/3;
        int empty=n;
        int count=0;
        while(empty/3>0){
            count+=water;
            empty=water+empty%3;
            water=empty/3;
        }
        if(empty==2){
            return count+1;
        }
        return count;
    }
    //字符串反转
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        int start=0;
        int end=str.length()-1;
        char[] ch=new char[str.length()];
        for(int i=0;i<ch.length;i++){
            ch[i]=str.charAt(i);
        }
        while(start<end){
            char tmp=ch[start];
            ch[start]=ch[end];
            ch[end]=tmp;
            end--;
            start++;
        }
        String str2=new String(ch);
        System.out.println(str2);
    }
}